A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
1. Field of the Invention
The present invention relates generally to information processing environments and, more particularly, to join operations in a data processing system, such as a Database Management System (DBMS).
2. Description of the Background Art
Computers are very powerful tools for storing and providing access to vast amounts of information. Computer databases are a common mechanism for storing information on computer systems while providing easy access to users. A typical database is an organized collection of related information stored as xe2x80x9crecordsxe2x80x9d having xe2x80x9cfieldsxe2x80x9d of information. As an example, a database of employees may have a record for each employee where each record contains fields designating specifics about the employee, such as name, home address, salary, and the like.
Between the actual physical database itself (i.e., the data actually stored on a storage device) and the users of the system, a database management system or DBMS is typically provided as a software cushion or layer. In essence, the DBMS shields the database user from knowing or even caring about underlying hardware-level details. Typically, all requests from users for access to the data are processed by the DBMS. For example, information may be added or removed from data files, information retrieved from or updated in such files, and so forth, all without user knowledge of underlying system implementation. In this manner, the DBMS provides users with a conceptual view of the database that is removed from the hardware level. The general construction and operation of a database management system is known in the art. See e.g., Date, C., xe2x80x9cAn Introduction to Database Systems,xe2x80x9d Volume I and II, Addison Wesley, 1990; the disclosure of which is hereby incorporated by reference.
DBMS systems have long since moved from a centralized mainframe environment to a de-centralized or distributed environment. One or more PC xe2x80x9cclientxe2x80x9d systems, for instance, may be connected via a network to one or more server-based database systems (SQL database server). Commercial examples of these xe2x80x9cclient/serverxe2x80x9d systems include Powersoft(copyright) clients connected to one or more Sybase( Adaptive Server(copyright) database servers. Both Powersoft(copyright) and Sybase(copyright) Adaptive Server(copyright) (formerly Sybase(copyright) SQL Server(copyright)) are available from Sybase, Inc. of Emeryville, Calif.
xe2x80x9cJoinxe2x80x9d is a common operation in an RDBMS. Nested Loop Join (NLJ), sort merge join, and hash join are the three well-known join methods. Optimization and execution of queries involving joins have been extensively discussed in the literature. See, e.g., Selinger, Patricia G., et. al., xe2x80x9cAccess Path Selection in a Relational Database Management System,xe2x80x9d ACM SIGMOD Conference, pp. 23 -34, 1979 which deals with finding optimal join orders and join methods to use. See, e.g., Shapiro, Leonard D., xe2x80x9cJoin Processing in Database Systems with Large Main Memories,xe2x80x9d TODS 11(3), pp. 239 -264, 1986 and Graefe, Goetz, et. al., xe2x80x9cHash Joins and Hash Teams in Microsoft SQL Server,xe2x80x9d VLDB, pp. 86 -97, 1998 which deal with merge joins and hash joins. See, e.g., Chen, Ming-Syan, et. al., xe2x80x9cOn Applying Hash Filters to Improving the Execution of Multi-Join Queries,xe2x80x9d VLDB Journal 6(2), pp. 121 -131, 1997 and Roussopoulos, Nick and Kang, Hyunchul, xe2x80x9cPipeline N-way Join Algorithm Based on the 2 -way Semijoinxe2x80x9d which deal with use of semijoin based approaches to process multi-join queries efficiently. See, e.g., O""Neil, Patrick E. and Graefe, Goetz, xe2x80x9cMulti-Table Joins Through Bitmapped Join Indices,xe2x80x9d SIGMOD Record 24(3), pp. 8 -11, 1995 which deals with using bitmapped join indices to process multi-table joins more efficiently. See, e.g., Dewitt, David J., et. al., xe2x80x9cNested Loops Revisited,xe2x80x9d PDIS, pp. 230 -242, 1993 which deals with parallelization of joins. The disclosures of the foregoing are hereby incorporated by reference.
What is needed is a technique that can be used to process some n-ary NLJs more efficiently, for n greater than 2, as queries with multiple joins are common in decision support and OLAP. The present invention fulfills this and other needs.
A database system implementing a methodology or technique that can be used to optimize processing of nested loop joins of three or more tables (n-ary NLJs for n greater than 2) more efficiently is described. The methodology is straightforward to implement and has been prototyped in a commercial RDBMS.
Operation of the methodology may be summarized as follows. First, a query is received (e.g., SQL-based query from a client database application) specifying a join of three or more tables, where at least one join condition exists between an inner table (in the join order) and an outer table that is not the immediately or directly preceding table (in the join order). The join order itself specifies the particular sequence or order that tables (or index) are accessed for retrieving rows (for examination) during query execution.
Query execution proceeds as follows. A loop is established to retrieve rows from successive tables (per the join order). The method determines whether a condition is being tested (i.e., value being compared) that refers back to a more-outer table that is not a directly preceding table. Consider the following example. query:
select [. . . ] from T1, T2, T3
where T1.C1=T2.C2
and T2.C2=T3.C3
and T1.C5=T3.C4
In the example, the join condition of T1.C5=T3.C4 requires a current row under examination from the third table in the join order (i.e., Table T3) to match the join condition (equality, in that example) specified for the first table (i.e., Table T1, which is not an immediately preceding table). If that condition is not met, then query execution (method) proceeds to fetch the next row (if any) from that outer table (whose just-tested condition failed).
Otherwise (i.e., the just-tested condition succeeds), the method continues down the join order to examine any remaining/subsequent tables in the join order (if any), applying any subsequent query conditions (if any) that must be met in order to qualify for the query. In the instance that a set of rows under examination meets the query condition(s), those rows are qualified (as having met the query). If any further rows/tables remain to be .examined, the method loops back to examine those rows/tables.
In implementation, upon encountering a failure condition (i.e., a given join condition does not hold true) from a join operator (scan child), context information (about the failure) is returned (to the n-ary nested-loop join operator) for indicating exactly which condition (i.e., join condition) failed. This information is tracked in a scan descriptor, which includes a xe2x80x9cfail sargxe2x80x9d data field indicating exactly which particular search argument (xe2x80x9csargxe2x80x9d ) failed. Based on this information, the system (operating through the n-ary nested-loop join operator) knows exactly which scan child to return back to (i.e., how far back to go in the join order to fetch the next row). In this manner, the methodology optimizes processing of n-ary nested loop joins by eliminating comparisons that will not hold true for the corresponding join condition (for which the comparisons were to be tested).